/*
	解法：使用一个长度为 26 的数组统计字母出现频率
	为什么：使用数组比 unordered_map 更高效、简洁
	时间复杂度：O(n)，空间复杂度：O(1)
 */

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution
{
public:
	bool isAnagram(string s, string t)
	{
		if (s.length() != t.length())
		{
			return false;
		}
		
		vector<int> count(26, 0); // 用来统计字符出现次数
		
		for (int i = 0; i < (int)s.length(); i++)
		{
			count[s[i] - 'a']++; //相当于一个简单的哈希函数，把字符映射到 count 数组对应位置上
			count[t[i] - 'a']--;
		}
		
		for (int i = 0; i < (int)count.size(); i++)
		{
			if (count[i] != 0)
			{
				return false;
			}
		}
		
		return true;
	}
};

int main()
{
	Solution solution;
	
	string s1 = "anagram";
	string t1 = "nagaram";
	
	string s2 = "rat";
	string t2 = "car";
	
	cout << boolalpha; // 打印 true/false 而不是 1/0
	cout << "Example 1: " << solution.isAnagram(s1, t1) << endl;
	cout << "Example 2: " << solution.isAnagram(s2, t2) << endl;
	
	return 0;
}

/*
	用unordered_map解题

  class Solution
  {
  public:
  bool isAnagram(string s, string t)
  {
  if (s.length() != t.length())
  {
  return false;
  }
  
  unordered_map<char, int> count;
  
  // 遍历字符串 s，统计字符出现次数
  for (int i = 0; i < s.length(); i++)
  {
  count[s[i]]++;
  }
  
  // 遍历字符串 t，减去字符出现次数
  for (int i = 0; i < t.length(); i++)
  {
  count[t[i]]--;
  }
  
  // 遍历哈希表，检查是否所有字符频次都为 0
  unordered_map<char, int>::iterator it;
  for (it = count.begin(); it != count.end(); ++it)
  {
  if (it->second != 0)
  {
  return false;
  }
  }
  
  return true;
  }
  };		

 */



